/*
https://leetcode.cn/problems/distinct-echo-substrings/solution/by-flix-zsuj/
 */
import java.util.HashSet;
import java.util.Set;

public class Solution1316 {
    public int distinctEchoSubstrings(String text) {
        Set<String> set=new HashSet<>();
        for (int i=0;i<text.length();i++){
            deal(text.substring(i),set);
        }
        return set.size();
    }

    private void deal(String s, Set<String> set) {
        int[] f=new int[s.length()];
        for (int i=1,j=0;i<s.length();i++){
            while (j!=0 && s.charAt(i)!=s.charAt(j)){
                j=f[j-1];
            }
            if (s.charAt(i)==s.charAt(j)){
                j++;
            }
            f[i]=j;
            if ((i+1)%(i+1-f[i])==0 && (i+1)/(i+1-f[i])%2==0){
               set.add(s.substring(0,i/2+1));
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1316().distinctEchoSubstrings("abcabcabc"));
    }
}
